package com.leetcode.math;

import java.util.*;

class RandomizedSet {

    private Map<Integer, Integer> indice;
    private List<Integer> arr;
    private Random random;

    /**
     * Initialize your data structure here.
     */
    public RandomizedSet() {
        indice = new HashMap<>();
        arr = new ArrayList<>();
        random = new Random();
    }

    /**
     * Inserts a value to the set. Returns true if the set did not already contain the specified element.
     */
    public boolean insert(int val) {
        if (!indice.containsKey(val)) {
            arr.add(val);
            indice.put(val, arr.size() - 1);
            return true;
        } else {
            return false;
        }
    }

    /**
     * Removes a value from the set. Returns true if the set contained the specified element.
     */
    public boolean remove(int val) {
        if (indice.containsKey(val)) {
            int tail = arr.size() - 1, removeIndex = indice.get(val);
            if (tail != removeIndex) {
                int swapVal = arr.get(tail);
                Collections.swap(arr, removeIndex, tail);
                indice.put(swapVal, removeIndex);
            }
            arr.remove(tail);
            indice.remove(val);
            return true;
        } else {
            return false;
        }
    }

    /**
     * Get a random element from the set.
     */
    public int getRandom() {
        if (arr.isEmpty()) return 0;
        int index = random.nextInt(arr.size() - 1);
        return arr.get(index);
    }
}
